密码学中的随机预言机及BLS签名安全证明

作者：Kobi Gurkan

译者：Kurt Pan

本文描述了随机性在密码协议中的作用和来源。

1背景

随机性在支撑区块链基础设施的密码学中无处不在—— 见于Merkle 树安全状态、工作量证明中的随机选择机制、权益证明中委员会的选择，以及支持可扩展性和隐私性的零知识证明之中。

哈希函数是这些协议中最重要的随机源。

2什么是哈希函数？

哈希函数接收“消息”（这可以是任何数据——区块链的状态、交易的内容等）并“吐出”在一些预定义的数字“空间”中的固定长度摘要。这个空间可能是所有到的数字，或者可以是素域的元素（在零知识证明中很常见），甚至有时是椭圆曲线点（它们是不同种类的数字）。

关键是，在实际计算哈希之前，给定输入的输出的“大小”应该是完全不可预测的。

哈希通常出现在两种情况中：

• 作为数据上的简短“唯一指纹”（通常是区块链的“状态”或交易内容）。

• 在某些“交互式协议”中替换验证者应提供的问题的方法。这是零知识证明的一个共同特点。交互式协议的安全性取决于“验证者”和“证明者”之间的一系列问题和答案。哈希可用于消除证明者（通常是消费者）和验证者（检查所有交易是否正确的区块链节点）之间直接来回对话的必要。

3哈希性质1：随机性

哈希函数的一个核心特性是它们以看似随机的方式对输入数据进行加扰。一个新提出的哈希函数，必须经过严格的统计测试，才能让密码学社区确信它确实表现出了其声称的随机性。任何不这样做的行为都会增加将依赖它们的协议暴露给潜在攻击者的可能。

这种随机性在许多情况下都很有用。

伪随机函数族 (PRF) 是类似于哈希函数的函数，将消息映射到输出，但另外还有一个密钥作为输入。PRF 可以由这些看似随机的哈希构造，然后PRF可用于构造消息认证码，以保护消息的认证性和完整性。

在将交互式证明转换为非交互式证明时，这些哈希也有帮助。如果在交互式证明中验证者向证明者发送均匀随机元素作为挑战，那么 Fiat-Shamir 启发式可以使用一个哈希将交互式随机挑战替换为到当前为止证明过程中消息的哈希，这将产生足够随机的元素。

4哈希性质2：抗碰撞性

此外，我们希望哈希函数具有：

• 抗碰撞性 - 很难找到产生相同结果的两个不同消息

• 抗原象性 - 给定一个输出，很难找到产生它的输入

• 抗第二原像性 - 给定一个输入和输出，很难找到另一个产生相同输出的输入

抗碰撞的愿望是直接的——如果两个不同的消息消生成同一个哈希，我们就无法再区分它们了。因此，我们希望短哈希摘要对于不同的消息尽可能唯一，以使不能恶意制作具有相同哈希的消息。根据经验，抗碰撞性通常比抗原象性更容易攻击。这是因为在抗碰撞性中你可以自由选择任何两个输入，而在抗原象性的两种变体中，都被限制为特定的输出。生日攻击立即将找到碰撞的复杂性降低到可能输出数量的平方根大小。通常，发现碰撞是应该逐步淘汰该哈希函数的强有力信号，因为它表明可能发生更严重的攻击。

它出现的另一个常见地方是在一些签名方案中：在 Schnorr 签名中我们需要一个hash to field，而在 BLS 签名中我们需要一个hash to group。在这两种情况下，哈希为我们提供了一个来自目标集合的唯一元素，该元素与哈希的其他结果无关。例如，我们不希望出现这种情况，即在 和 上调用哈希函数 ，也可以以某种方式推断.

5可证明安全和“标准模型”

哈希听起来非常有用！那么它有什么问题呢？

虽然对协议设计者很有用，但在协议中引入哈希函数会让密码学家很难证明协议的安全性。密码学家喜欢使用归约——你为你的协议制定一个安全性质，并表明如果该安全性质被敌手破坏，那么这意味着我们也解决了一个无法解决的问题，一个假设。

使用计算困难性假设来证明协议的安全性被认为是在标准模型中工作的。意思是你假设某些问题很困难，并尝试证明你协议的安全性质可以被解释为与这个问题一样困难。一个广为人知的这样的问题就是特定群中的离散对数问题：给定 和 ， 找到 使得. 如果有人想破坏你的协议的安全性质，而你已经证明要破坏意味着必须找到离散对数，那么你就处于一个非常好的状态之中。

一个具体的例子是 ElGamal 加密，我们有 IND-CPA 性质，粗略地说就是即使你知道密文是你选择的一系列明文之一的加密，你也无法知道实际是选择了个明文。如果该性质被破坏，则违背的假设是 DDH - Decisional Diffie Hellman：给定随机和群生成元，和是不可区分的。

哈希阻挠了这种可证明安全归约，限制了密码学家进行这种归约的能力，如果没有协议的另外的替代模型，我们将只能得到“已经尝试攻破该协议一段时间了，但是我们攻不破。”这样的结论，这感觉很不能令人满意。

6救援：随机预言机

随机预言机可以解决这个问题。

它提供了一种进行安全归约证明的方法，以获得对协议安全性的信心。在随机预言模型中工作时，我们用理想化的随机预言机来替换每个哈希函数：

• 当对新消息进行查询时，会返回来自目标集的从中均匀选取的随机响应。

• 当对之前查询过的消息进行查询时，返回与之前相同的响应。

7“可编程”随机预言机

可编程随机预言机允许一些参与者对其进行编程——即返回其选择的值，只要它们对接收者来说看起来是随机的。这听起来可能有点奇怪，因为我们在现实中使用的函数没有那个特性。鉴于它允许密码学家在某些协议的安全性上提供积极的结果，并且预言机的接受者并没有看到有什么不同（他们仍然看到的是随机值），这似乎是一个合理的权衡。

具体来说，我们可以允许想要打破假设的敌手，比如 DDH，去模拟另一个声称他们可以打破协议安全性质的敌手的环境。

通过对随机预言机进行编程，我们可以使用来自其环境的敌手的响应来打破假设。

还有一些其他不同的变体，提供不同的置信度 - 例如，不可编程随机预言机。

8并非完美

好吧，这听起来真的很强大。有什么问题？问题是随机预言并不真正存在。好的哈希只是近似地表现得像它们。

以最著名的哈希之一 SHA-256 为例。尝试输入一些数字，SHA(1)、SHA(2) 等。运行一些统计测试，看看数字网格的哪些“区域” 看起来是随机的。

根据定义，真正的随机函数并不存在——函数是算法性的、确定性的。更糟糕的是，由于随机预言机并不真正存在，因此存在一些病态的例子，一个方案在随机预言机模型中被证明是安全的，但在使用任何哈希函数实例化时却是不安全的。

那么这真的有用吗？它提供了一点信心，并有助于在协议的其他部分发现不良的协议设计错误。直观上如果你的哈希函数表现得像一个随机预言机，那么随机预言模型中的证明就在某种程度上是适用的；如果表现的不像，那么证明完全不适用。对于某些协议这也是我们所能得到的最好的结果，所以有总比没有好得多。

你可能还想知道 - 随机预言机的良好实例化是什么？当源和目标空间只是字节序列时，可以更轻松地直接从已知的哈希函数（如 SHA256）构建它们。而当我们谈论素域和椭圆曲线群时，难度会更大，会遇到很多陷阱。

Part1下一步是什么？

如果你想知道如何使用可编程随机预言机来证明著名的 BLS 签名方案的安全性，请阅读附录！

Part2附录

9BLS安全证明

BLS 签名的：

• 假设 - co-CDH: 给定 和 , 计算 是困难的。作为挑战给出 。

• 安全性质 - 存在不可伪造，给定公钥，即使看到不同消息上的一系列签名，也无法在没有访问私钥的情况下在另一条消息上伪造签名。

• 证明方法概览：

我们构造一个攻破 co-CDH的敌手。

声称攻破存在不可伪造性的敌手，接受一个公钥作为输入。和在挑战中收到的一样，和都不知道。在第一个得到不同消息的签名的阶段进行一系列随机预言查询，也进行签名查询。进行的随机预言查询个数要多于签名查询，因为在第一个要求得到签名的阶段，得到一个签名意味着一次随机预言查询加一次签名查询；而在伪造签名阶段，意味着一次随机预言查询而没有签名查询。

我们预先猜测 进行随机预言查询但不进行签名查询的那个消息的索引，这也将是为其伪造签名的消息。

在那些随机预言查询和签名查询都要求的查询中，我们必须提供可以通过BLS验证检验的应答，而且要看起来随机。选择一个随机数，计算。注意我们在不知道的情况下进行上述操作并且依然可以通过验证检验。

在那个仅仅进行随机预言查询的查询中，我们嵌入我们得到的挑战的剩余部分：。注意到在这种情况下如果被问到我们是无法计算的，因为我们不知道完整的指数，它不再只是了。也注意到因为看起来是随机的，这依然看起来随机。

因为知道如何伪造满足的签名，我们有。通过取我们得到了想要的！

10被攻破的 hash-to-curve

回想一下，我们正在寻找一个哈希，输入一条消息输出一个群元素。一个特别的已经被攻破的例子是通过两步来做：哈希到域接着乘以生成元。这种方法被攻破是因为给定一个签名，，其中是私钥，我们可以在不知道的情况下将其转换为一个对的签名，通过。